1. Field of the Invention
The present invention relates to a method of producing a data compression block code for any finite alphabet source with a given acceptable level of distortion.
2. The Prior Art
The method according to the present invention will produce a data compression block code for any finite alphabet source. The compression rates achievable by this design approach the theoretical limits of data compression as the block size increases.
In general, the present invention presents an efficient technique for data compression. Data compression, or source coding, is used in many technological fields which require transmission of data in a cost-effective and time-effective manner. In particular, the data to be transmitted is converted, using some algorithm, to more compact data which can be transmitted faster than the original source data. In the process of this conversion, errors are introduced creating what is known as distortion. A certain amount of distortion is acceptable, the amount depending upon the particular data and application involved.
Data compression is used in such areas as the transmission of text between two locations, such as facsimile transmission, or the transmission of data for storage such as in image processing. In fact, any type of information can be transmitted more efficiently using data compression techniques, such as through the airwaves, through wires, or between computer storage systems.
Fundamentally the problem of block coding a source (source coding) is to find vectors (code words) of size N which can be used to represent all the source vectors (source words) of size N. In its most abstract definition a source is simply defined to be a set of symbols (alphabet) along with a probability distribution specifying the chance of occurrence of each symbol. If there are r letters in the source alphabet then there are r.sup.N possible vectors of size N. The code words are vectors of size N made up from letters from a reproduction alphabet. If there are s letters in the reproduction alphabet then code words can be chosen from as many as s.sup.N reproduction words.
A person designing a code must specify how to choose M code words from the set of s.sup.N reproduction vectors and he must specify how to associate source words with code words. Usually he wants M to be much less than r.sup.N (compression) so that valuable resources (disk space, transmission energy, transmission time., etc.) are not wasted by representing the full set of r.sup.N messages. Since there are less code words than source words this necessarily means that many source words will be associated with, that is coded by, the same code word. The designer is willing to tolerate this distortion in exchange for the more beneficial efficiency of data compression.
The distortion produced can be quantitatively defined by an r.s distortion matrix {D(a,b)}, where each element of the matrix represents the distortion incurred by representing the source letter a by a reproduction letter b. The distortion between a source word and a code word is the sum of the distortion between each of the corresponding letters in each N-vector. The average distortion, Nd, for the code is the statistical average over all the source words. The average per letter distortion is d (=Nd/N).
When a set of M code words is specified, the association between source word and code word is usually defined by a simple distortion criterion. The code word used to code a source word is one which gives the least distortion.
The code designer is forever concerned with trade-offs between efficiency and distortion. In 1959 C. Shannon produced a theorem which shows the theoretical relationship between the compression rate and average distortion. The proof did not show how to construct a code which achieves the desired compression and distortion, but showed only how many code words would be needed for a given set of source words with a particular average distortion. The theorem has been proven in many ways since then but, until the Doctoral Thesis of the present inventor, (J. Nardi, "Practical Techniques for Source Coding: Constructive Block Coding and Calculating the Compression Rate of Sliding-Block Codes," Univ. of Maryland (1987), incorporated by reference herein and copy attached), there have been no proofs which suggest a practical construction of a code.
An exhaustive search and test of all M combinations of s.sup.N reproduction words will certainly produce an acceptable code, however even for moderate size blocks (8), a code of 5 words would require that over 1 million combinations be tested. This method would proceed more quickly if it could be demonstrated that less than s.sup.N words need to be tried as code word candidates.
In 1980, the present inventor developed a technique for constructing a code which encodes a binary memoryless (independent) source with limiting distortion d. By successively choosing code words to maximally cover particular source vectors, one can derive the same rate distortion function as that calculated by Shannon theory.
According to the 1980 technique, for a given word, of block size N, an acceptable block distortion is chosen. For example, a distortion of 2 means that two of the bits in the source vector are different from their corresponding bits in the reproduction vector, that is, an exclusive OR function: ##EQU1##
The first step is to select a starting reproduction vector and find all those source vectors which have a distortion equal to 2 with respect to the chosen reproduction vector. For the starting reproduction vector, the number of source vectors having a distortion of 2 is determined. The first code word is arbitrarily chosen from those reproduction vectors which correspond to the maximum number of source vectors with a distortion of 2. These source vectors are then eliminated from the list. The next code word is then taken from the list of reproduction vectors that yield the maximum count, i.e., have a distortion of 2 with respect to the most number of sources. Again, all the source vectors that have a distortion of 2 with respect to the new code word are then eliminated. This continues until all source vectors are eliminated or until no other code words correspond to that maximum number of source words.
This method had two major disadvantages. First, the source and reproduction alphabet was limited to the binary set {0,1}. Second, no control was allowed over the distortion matrix, which was limited to the exclusive OR distortion matrix.
Other prior techniques of data compression allowed for picking a source code for a given distortion rate using algebraic codes or annealing codes. Both these prior methods were inefficient in that too much processing time was required, too many codes were produced, more than were required, and the user had no control over the distortion which resulted.
The technique according to the present invention differs from methods used in the previous work of Wolfowitz, Csiszar, and Korner (J. Wolfowitz, "Coding Theorems of Information Theory," Erg. Math. (N.F.)31. Berlin-Gottingen-Heidielberg: Springer-Verlag (1959), I, Csiszar and J. Kroner, Information Theory: Coding for Discrete Memoryless Systems, New York: Academic Press (1981)) in that the set of block vectors from which code words are chosen is much smaller and thus easier and quicker to search. The method differs from the Nardi, Davisson results of 1980 (J. Nardi and L. Davisson, "Constructive Method for Calculating R(d)," Proceedings of the 1980 Conference on Information Sciences, Dept. of Elec. Eng., Princeton, N.J. p. 163 (1980)) in that the current technique applies to sources of arbitrary alphabets having any number of symbols, not just binary sources, and it applies to arbitrary distortion matrices, not just the fidelity criterion.
The algorithm according to the present invention uses only strictly typical vectors, which constitutes many less vectors than s.sup.N, thus this method of choosing code words is much faster. The work of Wolfowitz is based on searches of typical sets which, although less numerous than the full set of code words, are still much more numerous than the strictly typical set. The work of Csiszar and Korner also uses typical sets. The work of Wolfowitz, Csiszar, Korner also used the more general idea of covering.
The work of Nardi, Davisson used strictly typical sets but was only applicable to binary sources (alphabet={0,1}) with a particular distortion matrix: ##EQU2## That work also differed because the previous method of choosing code words was based on a less general idea of maximizing distortion spheres rather than maximizing covering spheres as in the present invention.